package com.lry.basic.algorithm.recursion;

import java.util.ArrayList;
import java.util.List;

class Combine {

    List<List<Integer>> res = new ArrayList();


    public static void main(String[] args) {
        System.out.println(new Combine().combine(4, 2));
    }

    public List<List<Integer>> combine(int n, int k) {

        List<Integer> list = new ArrayList();

        dfs(n,k,1,list);

        return res;
    }

    public void dfs(int n,int k,int i,List<Integer> list){
        if(list.size()==k){
            res.add(new ArrayList<Integer>(list));
            return;
        }
        if(i>n){
            return;
        }
        list.add(i);

        dfs(n,k,i+1,list);

        list.remove(list.size()-1);

        dfs(n,k,i+1,list);
    }

}